#include<iostream>
#include<utility>
#include<vector>
#include<queue>
using namespace std;
int n, m;

struct Node{
    int index, dis;
    Node(int a = 0, int b = 0):index(a), dis(b){};
};

bool operator < (Node a, Node b){ //返回true时，说明a的优先级低于b
    return a.dis > b.dis;
}


int main()
{
    cin >> n >> m;

    vector<vector<int> > v(n+1, vector<int>(n+1, 0));
    vector<bool> visited(n+1, false);
    vector<bool> open(n+1, false);
    vector<int> ans(n+1, -1);
    priority_queue<Node> pq;

    int tmp1, tmp2, z;
    for(int i = 0; i < m; i++)
    {
        cin >> tmp1 >> tmp2 >> z;
        v[tmp1][tmp2] = z;
    }
    Node *node = new Node[n+1];
    node[1] = Node(1, 0);
    pq.push(Node(1, 0));
    open[1] = true;
    for(int i = 2; i <= n; i++)
    {
        node[i] = Node(i, 100001);
    }
    int count = 0;
    while(pq.size())
    {
        auto tmp = pq.top();  // auto yyds
        pq.pop();
        
        int index = tmp.index;
        int dis = tmp.dis;
        if(visited[index]) continue;
        // if(index != 2)
            // cout << index << dis << visited[index] << endl;
        for(int i = 1; i <= n; i++)
        {
            if(v[index][i] && !visited[i])
            {
                if(dis + v[index][i] < node[i].dis)
                {
                    node[i].dis = dis + v[index][i];
                    pq.push(node[i]);
                }
                
            }
            // cout << node[i].dis << " ";
        }
        // cout << endl;
        if(dis == 100001)
            break;
        if(!visited[index]) 
        {
            // cout << dis << endl;
            count++;
            ans[index] = dis;
        }
        
        if(count == n) break;
         
        // open[index] = false;
        visited[index] = true;
    }
    
    for(int i = 1; i <= n; i++)
    {
        cout << ans[i] << " ";
    }
    return 0;
}





